package com.mango.leet.code.spring.team;

/**
 * 2. 信物传送
 * @Author: mango
 * @Date: 2022/4/23 3:13 下午
 */

import java.util.*;

/**
 * 欢迎各位勇者来到力扣城，本次试炼主题为「信物传送」。
 *
 * 本次试炼场地设有若干传送带，matrix[i][j] 表示第 i 行 j 列的传送带运作方向，"^","v","<",">" 这四种符号分别表示 上、下、左、右 四个方向。信物会随传送带的方向移动。勇者每一次施法操作，可临时变更一处传送带的方向，在物品经过后传送带恢复原方向。
 * lcp (2).gif
 *
 * 通关信物初始位于坐标 start处，勇者需要将其移动到坐标 end 处，请返回勇者施法操作的最少次数。
 *
 * 注意：
 *
 * start 和 end 的格式均为 [i,j]
 * 示例 1:
 *
 * 输入：matrix = [">>v","v^<","<><"], start = [0,1], end = [2,0]
 *
 * 输出：1
 *
 * 解释：
 * 如上图所示
 * 当信物移动到 [1,1] 时，勇者施法一次将 [1,1] 的传送方向 ^ 从变更为 <
 * 从而信物移动到 [1,0]，后续到达 end 位置
 * 因此勇者最少需要施法操作 1 次
 *
 * 示例 2:
 *
 * 输入：matrix = [">>v",">>v","^<<"], start = [0,0], end = [1,1]
 *
 * 输出：0
 *
 * 解释：勇者无需施法，信物将自动传送至 end 位置
 *
 * 示例 3:
 *
 * 输入：matrix = [">^^>","<^v>","^v^<"], start = [0,0], end = [1,3]
 *
 * 输出：3
 *
 * 提示：
 *
 * matrix 中仅包含 '^'、'v'、'<'、'>'
 * 0 < matrix.length <= 100
 * 0 < matrix[i].length <= 100
 * 0 <= start[0],end[0] < matrix.length
 * 0 <= start[1],end[1] < matrix[i].length
 */
public class T2 {
    public static void main(String[] args) {
        String[] matrix = {">>v","v^<","<><"};
        int[] start = {0,1}, end = {2,0};

        //String[] matrix = {">^^>","<^v>","^v^<"};
        //int[] start = {0,0}, end = {1,3};
        System.out.println(new Solution().conveyorBelt(matrix,start,end));
    }
    static class Solution {
        public int conveyorBelt(String[] matrix, int[] start, int[] end) {
            // 已经走过的路
            Set<int[]> goSet = new HashSet<>();
            int result = 0;
            int row  = matrix.length;
            int col = matrix[0].length();
            // 设置起点
            Queue<int[]> queue = new LinkedList<>();
            queue.add(start);
            goSet.add(start);
            boolean find = false;
            while (!queue.isEmpty()){
                int[] cur = queue.poll();
                // 判断是否到达end
                if(cur[0] == end[0] && cur[1] == end[1]){
                    // 到达直接返回
                    find = true;
                    break;
                }
                char c = matrix[cur[0]].charAt(cur[1]);
                int r = cur[0];
                int l = cur[1];
                if(c == '>'){
                    l ++;
                }else if(c == 'v'){
                    r ++;
                }else if(c == '<'){
                    l --;
                }else if(c == '^'){
                    r --;
                }
                // 判断得到的下一个点位置是否合适（没超出，且没在已经走过的路里）
                boolean needMagic = false;
                if(r>=0 && r<= row && l>=0 && l<= col){
                    int[] next = new int[]{r,l};
                    if(!inSet(goSet,next)){
                        queue.add(next);
                        goSet.add(next);
                    }else{
                        // 已经走过
                        needMagic = true;
                    }
                }else{
                    needMagic = true;
                }
                // 施法
                if(needMagic){
                    // 上下左右
                    int[][] nexts = new int[][]{{r,l-1},{r,l+1},{r-1,l},{r+1,l}};
                    for(int[] next : nexts){
                        // 点在范围内且不在走过的路里
                        if(next[0]>=0 && next[0]<= row && next[1]>=0 && next[1]<= col && !goSet.contains(next)){
                            if(r<end[0]){

                            }
                        }
                    }

                    result ++;
                }
            }
            return result;
        }

        public boolean inSet(Set<int[]> set,int[] node){
            for(int[] k : set){
                if(k[0] == node[0] && k[1] == node[1]){
                    return true;
                }
            }
            return false;
        }
    }
}
